#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct LNode* PtrToNode;
struct LNode {
    int Data;
    PtrToNode Next;
};
typedef PtrToNode Position;
typedef PtrToNode List;

List MakeEmpty ();

int FindKth ( List L, int K );

Position Find ( List L, int X );

bool Insert ( List L, int X, int i );

bool Delete ( List L, int i );

int Length ( List L );

int main (void) {
    List L;
    int num, X, i, choice;
    bool result;
    L = MakeEmpty();
    
    // /* insert */
    // printf("Input\nPlease input how much data you want to insert\n");
    // scanf("%d",&num);
    // for( i = 1; i <= num; i++ ) {
    //     printf("Insert from begin to end\nPlease insert the %dst data\n",i);
    //     scanf("%d",&X);
    //     Insert(L, X, i);
    // }

    while (1) {
        printf("input choice:\n1  insert\t2  delete\n3  exit\t\t4  print\n");
        scanf("%d",&choice);
        switch (choice) {
        case 1:
            printf("Please input place and value\n");
            scanf("%d %d",&i, &X);
            if ( i <= 1 && i > Length(L) ) {
                printf("Err place\n");
                break;
            }
            result = Insert(L, X, i);
            if ( result == true ) printf("Insert Success\n");
            else printf("Insert Failure\n");
            break;
        case 2:
            printf("Please input place to delete\n");
            scanf("%d",&i);
            if ( i <= 1 && i > Length(L) ) {
                printf("Err place\n");
                break;
            }
            result = Delete(L, i);
            if ( result == true ) printf("Delete Success\n");
            else printf("Delete Failure\n");
            break;
        case 3:
            for( i = 1; i <= Length(L); i++ ) {
                Delete(L,i);
            }
            printf("exit success\n");
            exit(-9);
            break;
        case 4:
            printf("Data:\n");
            for( i = 1; i <= Length(L); i++ ) {
                X = FindKth(L,i);
                printf("%d\t|\t%d\n",i,X);
            }
            break;
        default:
            printf("NULL\n");
            break;
        }
    }
    

    return EXIT_SUCCESS;
}

List MakeEmpty () {
    List head = NULL, tail = NULL, p;
    int i,num,X;
    
    printf("Please input the number of datum\n");
    scanf("%d",&num);
    for ( i = 0; i < num; i++ ) {
        printf("Please input the %dst data\n",i+1);
        scanf("%d",&X);
        p = (List)malloc(sizeof(struct LNode));
        p->Data = X;
        p->Next = NULL;
        if ( head == NULL ) {
            head = p;
        } else {
            tail->Next = p;
        }
        tail = p;
    }
    return head;
}

int FindKth ( List L, int K ) {
    Position p;
    int cnt = 1;
    p = L;
    while ( p && cnt < K ) {
        p = p->Next;
        cnt++;
    }
    if ( ( cnt == K ) && p ) return p->Data;
    else return -1;
}

Position Find ( List L, int X ) {
    Position p = L;
    while ( p && p->Data != X ) p = p->Next;
    if (p) return p;
    else return NULL;
}

bool Insert ( List L, int X, int i ) {
    Position tmp, pre;
    int cnt = 0;

    if ( i == 1 ) {
        printf("No head while inserting\n");
        return false;
    }
    pre = L;
    while ( pre && cnt < i - 1 ) {
        pre = pre->Next;
        cnt++;
    }
    if ( pre == NULL || cnt != i - 1 ) {
        printf("Wrong place while inserting\n");
        return false;
    } else {
        tmp = (Position)malloc(sizeof(struct LNode));
        tmp->Data = X;
        tmp->Next = pre->Next;
        pre->Next = tmp;
        return true;
    }
}

bool Delete ( List L, int i ) {
    Position tmp, pre;
    int cnt = 0;

    pre = L;
    while ( pre && cnt < i - 1 ) {
        pre = pre->Next;
        cnt++;
    }

    if ( pre == NULL || cnt != i - 1 || pre->Next == NULL ) {
        printf("Err while deleting\n");
        return false;
    } else {
        tmp = pre->Next;
        pre->Next = tmp->Next;
        free(tmp);
        return true;
    }
    
}

int Length ( List L ) {
    Position p;
    int cnt = 0;
    p = L;
    while ( p ) {
        p = p->Next;
        cnt++;
    }
    return cnt;
}